//
//  46. 全排列.swift
//  Top600
//
//  Created by rjb on 2021/8/9.
//

import Foundation

class Solution46 {
    // 全排列
    // 采用回溯法，回溯方法其实就是树形结构
    var result: [[Int]] = []
    var path: [Int] = []
    func permute(_ nums: [Int]) -> [[Int]] {
        backTrace(nums, start: 0)
        return result
    }
    
    func backTrace(_ nums: [Int], start: Int) {
        if nums.count == 0 {
            result.append(path)
            return
        }
        for i in start..<nums.count {
            path.append(nums[i])
            var nextArray = nums
            nextArray.remove(at: i)
            backTrace(nextArray, start: 0)
            path.removeLast()
        }
    }
    
    static func test() {
        let solution = Solution46()
        let nums = [1,2,3]
        let result =  solution.permute(nums)
        print(result)
    }
}
